package binary_search.leetcode_240;

public class SearchMatrix {
    /**
     *  二分查找解法：
     *          对每一行进行二分搜索。
     *
     *  二分查找只利用了行有序这个条件，不是最好的解法，最好的解法参考剑指第4题
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        for(int i = 0; i < matrix.length; i++){
            //如果当前行的第一元素都 > target 则后面的都不用找了，直接返回false
            if(matrix[i][0] > target){
                break;
            }
            //如果当前行的最后一个元素 < target， 则当前行不用找了，直接开始下一行
            if(matrix[i][matrix[0].length - 1] < target){
                continue;
            }
            if (binarySearch(matrix[i], target)){
                return true;
            }
        }
        return false;
    }
    public boolean binarySearch(int[] nums, int target){
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return true;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        return false;
    }
}
